题面

$2-SAT$ 问题的相关应用

解题思路

$2-SAT+SCC$

分析

由于条件限制，每场比赛只能由两种车参加，因此就能把三种车型缩成两种，比如，当前的地图类型为 $a$，那么只用 $B$ 和 $C$ 类型车能使用，这样就能把三种状态缩成两种状态，用 $2-SAT$ 解决即可

考虑如何处理 $x$ 类型地图

由于 $x$ 类型地图的数量很少，最多只有 $8$ 个，因此可以考虑枚举 $x$ 类地图的状态，即可以将 $x$ 类型地图看做其他类型的地图，但这样的复杂度是 $O(3^8(n+m))$，稳 $T$。不过不难发现，将 $x$ 类地图看做 $a$ 类地图时，$B$ 和 $C$ 车能在该地图上使用，将 $x$ 类地图看做 $b$ 类地图时，$A$ 和 $C$ 车能在该地图上使用，这样三种车都出现过了，因此枚举三种状态是无必要的，只要枚举两种状态即可，这样复杂度就降至了 $O(2^8(n+m))$

考虑如何建图

对于每个限制，当然要判断这种限制是否合法，比如如下样例：

10 0
abbbacabab
20
5 A 3 B
9 A 4 C
4 C 10 A
8 B 3 C
6 C 10 A
5 A 9 C
8 A 2 C
5 A 8 B
10 A 10 A
5 B 4 B
6 C 10 C
2 C 4 B
5 C 7 B
5 A 10 B
3 A 7 B
6 B 4 B
3 C 8 B
1 B 3 B
4 B 3 C
8 A 2 A
CAAACABCBA

对于上述第 $13$ 行的限制，当第 $5$ 场比赛使用 $B$ 类车时，第 $4$ 场比赛必须用 $B$ 类车，显然对于第 $4$ 场比赛，这是不合法的，但是这个条件仍然是有约束力的，即造成第 $5$ 场比赛不能使用 $B$ 类车，那么如何建图维护这种约束呢？

显然，我们只需要连一条 $5B$ 向 $5C$ 的单向边即可，这样就表明如果取 $5B$ 那么一定要取 $5C$ ，明显是不合法的，最后输出方案的时候就不会输出 $5B$

也有可能形如上述第 $4$ 行的限制，这种限制由于没有 $5A$ 这个节点，也连不出边，直接舍弃即可

其他一般情况下，由于限制类型是 ，因此一方面要建 的边，同时也要建 的边

Warning

1、上述的两种情况

2、数组大小

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 100007
#define N 50003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline int getc() {
    rgt char c=getchar();
    while(c<'A'||c>'Z') c=getchar();
    return (c-'A');
}
struct node{
    int x,y,vx,vy;
    inline void in() {x=read(),vx=getc(),y=read(),vy=getc();}
}b[M];
int head[N<<1],ver[M<<1],nxt[M<<1],n,m,t,d,num,ans,p[11];
int dfn[N<<1],low[N<<1],St[N<<1],bl[N<<1],res,top,D;
char s[N];
inline void add(rint x,rint y) {//建单向边
    ver[++t]=y,nxt[t]=head[x],head[x]=t;
}
inline void tarjan(rint k) {//求SCC
    rint i,to;
    dfn[k]=low[k]=++num,St[++top]=k;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(!dfn[to]) tarjan(to),cmin(low[k],low[to]);
        else if(!bl[to]) cmin(low[k],dfn[to]);
    }
    if(dfn[k]==low[k]) {
        bl[k]=++res;
        while(St[top]!=k)
            bl[St[top--]]=res;
        --top;
    }
}
int main()
{
    rint i,j,x,y,vx,vy;
    n=read(),d=read(),scanf("%s",s+1),m=read();
    for(i=1;i<=m;i++) b[i].in();D=1<<d;
    for(i=1;i<=n;i++) if(s[i]=='x') p[t++]=i;
    for(j=0;j<D;j++) {//枚举x图状态
        for(t=0;t<d;++t) s[p[t]]=(j>>t)&1?'a':'b';//更新状态
        t=num=res=0,ans=1;
        memset(bl,0,(n+1)<<3),
        memset(dfn,0,(n+1)<<3),
        memset(head,0,(n+1)<<3);//初始化
        for(i=1;i<=m;i++) {
            x=b[i].x,y=b[i].y;
            if(b[i].vx==s[x]-'a') continue;//无用的限制
            if(s[x]=='c') vx=b[i].vx>0;
            else vx=b[i].vx>1;
            if(b[i].vy==s[y]-'a') add(x+vx*n,x+(vx^1)*n);//一个点不能取的限制
            else {//一般情况
                if(s[y]=='c') vy=b[i].vy>0;
                else vy=b[i].vy>1;
                add(x+vx*n,y+vy*n),
                add(y+(vy^1)*n,x+(vx^1)*n);
            }
        }
        for(i=1;i<=(n<<1);i++) if(!dfn[i]) tarjan(i);
        for(i=1;i<=n;i++) if(bl[i]==bl[i+n]) {ans=0;break;}
        if(ans) {
            for(i=1;i<=n;i++) {
                x=bl[i]<bl[i+n];//小的先选肯定是最优的
                if(s[i]=='a') printf("%c",x?'B':'C');
                else if(s[i]=='b') printf("%c",x?'A':'C');
                else printf("%c",x?'A':'B');//分情况讨论
            }
            return 0;
        }
    }
    printf("-1");
    return 0;
}

devil.